/*
提交链接：https://leetcode.cn/problems/number-of-islands/submissions/573560293
200. 岛屿数量-中等
完成日期：2024/10/17
并查集
*/

class UnionFind {
public:
    UnionFind(int size) : parent(size), rank(size, 0) {
        for (int i = 0; i < size; ++i) {
            parent[i] = i; // 初始化，每个节点的父节点为自己
        }
    }
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            // 按秩合并
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
private:
    vector<int> parent; // 存储父节点
    vector<int> rank;   // 存储树的秩
};
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty()) return 0;
        int rows = grid.size();
        int cols = grid[0].size();
        UnionFind uf(rows * cols);
        int numIslands = 0;
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == '1') {
                    numIslands++; // 新岛屿
                    // 将当前坐标转化为并查集的索引
                    int index = i * cols + j;
                    // 检查相邻的上下左右位置
                    if (i > 0 && grid[i - 1][j] == '1') {
                        uf.unionSets(index, (i - 1) * cols + j);
                    }
                    if (i < rows - 1 && grid[i + 1][j] == '1') {
                        uf.unionSets(index, (i + 1) * cols + j);
                    }
                    if (j > 0 && grid[i][j - 1] == '1') {
                        uf.unionSets(index, i * cols + (j - 1));
                    }
                    if (j < cols - 1 && grid[i][j + 1] == '1') {
                        uf.unionSets(index, i * cols + (j + 1));
                    }
                }
            }
        }
        // 统计不同的岛屿根
        int uniqueIslands = 0;
        vector<int> rootSet; // 存储根节点
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                if (grid[i][j] == '1') {
                    int root = uf.find(i * cols + j);
                    if (find(rootSet.begin(), rootSet.end(), root) == rootSet.end()) {
                        rootSet.push_back(root); // 添加新的根节点
                        uniqueIslands++;
                    }
                }
            }
        }
        return uniqueIslands;
    }
};